import org.junit.Test;

import java.util.Arrays;

/**
 * __|__ __|__
 * _|_   _|_
 * .---. .---.
 * |___| |___|
 * _\_/_ _\_/_
 * _X_   _X_
 * |   | |   |
 * |___| |___|
 *
 * @Author zhaoyi
 * @date 2020/4/7
 */
public class MergeArray {


    /**
     * 合并两个有序数组,对比下合并两个有序链表
     * https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/8/sorting-and-searching/52/
     */
    @Test
    public void test1() {


        int[] nums1 = {0};
        int[] nums2 = {2};
        merge(nums1, 0, nums2, 1);
        System.out.println(Arrays.toString(nums1));

        //别人版本的
        int[] nums11 = {1, 2, 3, 0, 0, 0};
        int[] nums22 = {2, 5, 6};
        mergeOther(nums11, 3, nums22, 3);
        System.out.println(Arrays.toString(nums11));


    }

    /**
     * 别人的版本感觉简洁很多
     * 核心思想从后往前放
     */
    public void mergeOther(int[] nums1, int m, int[] nums2, int n) {
        int p = m + n - 1;
        int i = m - 1, j = n - 1;
        while (i >= 0 && j >= 0) {
            if (nums1[i] > nums2[j]) {
                nums1[p--] = nums1[i--];
            } else {
                nums1[p--] = nums2[j--];
            }
        }
        while (i >= 0) nums1[p--] = nums1[i--];
        while (j >= 0) nums1[p--] = nums2[j--];
    }


    /**
     * 合并两个有序数组
     */
    private void merge(int[] nums1, int m, int[] nums2, int n) {
        if (m == 0) {
            for (int i = 0; i < n; i++) {
                nums1[i] = nums2[i];
            }
        }
        if (n == 0) {
            return;
        }
        int j = 0;
        int i = 0;
        boolean flag = false;

        for (int k = 0; k < m; k++) {
            for (int l = j; l < n; l++) {
                //nums2当前值大于等于nums1的,直接break不用比较后面的了
                if (nums2[l] >= nums1[k]) {
                    break;
                }
                j++;
                flag = true;
            }
            if (flag) {
                k = movesSet(nums1, nums2, k, i, j, m);
                m = m + j - i;
                flag = false;
                i = j;
            }
            if (k == m - 1) {
                //nums1遍历完了 都没nums2剩余的大
                for (int l = j; l < n; l++) {
                    nums1[++k] = nums2[l];
                }
            }
        }
    }

    private int movesSet(int[] nums1, int[] nums2, int k, int i, int j, int m) {
        //把nums1从K开始所有向后移动step位
        int step = j - i;
        int left = m - 1;
        for (int l = left; l >= k; l--) {
            nums1[l + step] = nums1[l];
        }

        //把nums2的数据放入nums1
        for (int l = 0; l < step; l++) {
            nums1[k] = nums2[i];
            k++;
            i++;
        }

        return k;
    }


}
